package leetcode_双指针;

import general_class.ListNode;

/**
 * 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 算法：双指针（快慢指针）
 * 长度 L, 倒数第 n 个数(正数第 L - n + 1 个), 删除倒数第 n 个数, 要找到正数第 (L - n) 个数
 * f 从 第一个节点 出发, 走 n 次, 还剩下 L - n 个位置没有走,
 * 此时 s 从 第一个节点 出发, 与 f 一起走, 当 f 走到最后一个节点时, s 走到第 (L - n) 个位置, 走了 (L - n) 步
 * 因为可能要删除倒数第 L 个数, 所以需要在头前加上假节点, 表示第 0 个节点, 所以 s 要从第 0 个位置走, 需要走 (L - n + 1) 步
 * 此时, f 要再走一步, 变为 null
 *
 * @author yzh
 * @version 1.0
 * @date 2022/3/21 22:21
 */
public class _19 {

    public static ListNode removeNthFromEnd_new(ListNode head, int n) {
        // 有可能删除头节点, 所以定义一个假的头节点
        // dummy 1 2 3 4 5 6
        // fast 走 n 步, 到第 n + 1 个位置(下标从 1 开始)
        ListNode dummy = new ListNode(), fast = dummy, slow = dummy;
        dummy.next = head;
        while (n-- > 0) fast = fast.next;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode f = head;
        while (n-- > 0) f = f.next;
        ListNode ans = new ListNode(), s = ans;
        ans.next = head;
        while (f != null) {
            s = s.next;
            f = f.next;
        }
        s.next = s.next.next;
        return ans.next;
    }

}
